package com.my.ruyi;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class AllSort {

	public static void main(String[] args) {
		Integer[] arr = new Integer[] {9,7,8,10,15,1,3,2,4};
		//ShellSort(arr);
		Integer[] result = new Integer[arr.length];
		//mergeSort(arr, result, 0, arr.length - 1);
		//mergeSortIterable(arr, result);
		//quickSort(arr, 0, arr.length -1);
		//selectionSort(arr);
		bucketSort(arr);
		System.out.println(Arrays.toString(arr));
		
		/*int start = 3;
		
		start += 4 * 2;
		System.out.println(start);*/
	}
	
	/**
	 * 插入排序
	 * ? extend T: 表示?是继承自T
	 * ? super T: 表示?是T的超类
	 * 第一个认为是已排序的，从后面未排序的序列中依次取出，插入到前面已排序的序列中
	 * @param a
	 */
	public static <T extends Comparable<? super T>> void  InsertionSort(T[] a) {
		int j;
		for (int i = 1; i < a.length; i++) {
			T temp = a[i]; // 额外的空间

			for (j = i; j > 0 && temp.compareTo(a[j-1]) < 0; j--) {
				a[j] = a[j-1];
			}
			a[j] = temp;
		}
	}
	
	public static void insertion_sort( int[] arr ){
	    for( int i=0; i<arr.length-1; i++ ) {	
	        for( int j=i+1; j>0; j-- ) {
	            if( arr[j-1] <= arr[j] )
	                break;
	            int temp = arr[j];
	            arr[j] = arr[j-1];
	            arr[j-1] = temp;
	        }
	    }
	}
	
	
	/**
	 * 希尔排序
	 * 基于插入排序，使数组中任意间隔为h的元素都是有序的，
	 * 即将全部元素分为h个区域使用插入排序。
	 * @param a
	 */
	public static <T extends Comparable<? super T>> void ShellSort(T[] a) {
		int j;
		
		for (int gap = a.length / 2; gap > 0; gap /= 2) {
			// 插入排序
			for (int i = gap; i < a.length; i++) {
				T temp = a[i];
				// 此处 小于号是升序，大于号是降序
				for (j = i; j >= gap && temp.compareTo(a[j - gap]) < 0; j -= gap) {
					a[j] = a[j - gap];
				}
				a[j] = temp;
			}
		}
	}
	
	
	private static <T extends Comparable<? super T>> void swap(T[] arr, int i,int j){
        T temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
	
	/**
	 * 调整堆
	 * 构建大根堆和小根堆都是自底向上的方法，建堆过程时间复杂度为  O(2N)
	 * 堆排过程中总的时间复杂度为  O(NlogN)
	 * @param arr: 数组
	 * @param index: 需要堆化处理的数据的索引
	 * @param len: 未排序的堆（数组）的长度
	 */
	public static <T extends Comparable<? super T>> void maxHeapify(T[] arr, int index, int len){
		int li = (index << 1) + 1; // index节点的左子节点索引
		int ri = li + 1; // index节点的右子节点索引
		int cMax = li;   // 子节点值最大索引，默认左子节点。
		
		if (li > len) return;
		// 判断左右子节点，哪个大
		if (ri <= len && arr[ri].compareTo(arr[li]) > 0) {
			cMax = ri;
		}
		
		// cmax的值大于 父节点index处的值
		if (arr[cMax].compareTo(arr[index]) > 0) {
			swap(arr, cMax, index);      // 如果父节点被子节点调换，
			maxHeapify(arr, cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
		}
	}
	
	/**
	 * 堆排序
	 * @param arr
	 */
	public static <T extends Comparable<? super T>> void heapSort(T[] arr) {
		/*
         *  第一步：将数组堆化
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
         */
        int len = arr.length - 1;
        int beginIndex = (len - 1) >> 1; 
        for(int i = beginIndex; i >= 0; i--){
            maxHeapify(arr, i, len);
        }
        
        /*
         * 第二步：对堆化数据排序
         * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for(int i = len; i > 0; i--){
            swap(arr, 0, i);
            maxHeapify(arr, 0, i - 1);
        }
        
        System.out.println(Arrays.toString(arr));
	}
	
	/**
	 * 归并排序
	 * 递归方式实现
	 * @param arr
	 */
	public static <T extends Comparable<? super T>> void mergeSort(T[] arr, T[] result, int start, int end) {
		if (start < end) {
			int mid = (start + end) / 2;
			mergeSort(arr, result, start, mid);
			mergeSort(arr, result, mid + 1, end);
			mergeArray(arr, result, start, mid, end);
		}
	}
	
	/**
	 * 将合并成有序序列
	 * @param arr
	 * @param result
	 * @param start
	 * @param mid
	 * @param end
	 */
	private static <T extends Comparable<? super T>> void mergeArray(T[] arr, T[] result, int start, int mid, int end) {
		int i = start, j = mid + 1;
		int m = mid, n = end;
		int k = 0;
		// 交换start-mid   (mid+1)-end
		while (i <= m && j <= n) {
			// <=升序     >=升序
			if (arr[i].compareTo(arr[j]) <= 0) {
				result[k++] = arr[i++];
			} else {
				result[k++] = arr[j++];
			}
		}
		
		// start--mid
		while (i <= m) {
			result[k++] = arr[i++];
		}
		
		while (j <= n) {
			result[k++] = arr[j++];
		}
		
		for (i = 0; i < k; i++) {
			arr[start + i] = result[i];
		}
	}
	
	/**
	 * 归并排序
	 * 迭代方式实现
	 * @param arr
	 */
	public static <T extends Comparable<? super T>> void mergeSortIterable(T[] arr, T[] result) {
		int len = arr.length;
		int step = 1, start = 0;
		
		for (step = 1; step < len; step *= 2) {
			for(start = 0; start < len; start += (step * 2)) {
				int low = start;
				int mid = (start + step) < len ? (start + step) : len;
				int high = (start + 2 * step) < len ? (start + 2 * step) : len;
				//两个块的起始下标及结束下标
	            int start1 = low, end1 = mid;
	            int start2 = mid, end2 = high;
				while (start1 < end1 && start2 < end2) {
					// < 0 是升序，> 0 降序
					result[low++] = arr[start1].compareTo(arr[start2]) < 0 ? arr[start1++] : arr[start2++];
				}
				while(start1 < end1) {
			        result[low++] = arr[start1++];
		        }
	            while(start2 < end2) {
	            	result[low++] = arr[start2++];
	            }
			}
			
			T[] temp = arr;
			arr = result;
			result = temp;
		}
	}

	/**
	 * 快速排序
	 * @param arr
	 * @param start
	 * @param end
	 */
	public static <T extends Comparable<? super T>> void quickSort(T[] arr, int start, int end) {
		if (start >= end || arr == null || arr.length <= 1) return;
		
		// 选取基准点
		int i = start, j = end;
		T pivot = arr[(start + end) / 2]; 
		
		while(i <= j) {
			// 小于基准点--从头部开始   <0升序  >0降序
			while (arr[i].compareTo(pivot) < 0) {
				i++;
			}
			// 大于基准点--从尾部开始  >0升序  <0降序
			while (arr[j].compareTo(pivot) > 0) {
				j--;
			}
			// 交换 基准点两侧的数据
			if (i < j) {
				T t = arr[i];
				arr[i] = arr[j];
				arr[j] = t;
				++i;
				--j;
			} else if (i == j) {
				++i;
			}
		}
		
		quickSort(arr, start, j);
		quickSort(arr, i, end);
	}
	
	
	/**
	 * 选择排序
	 * @param arr
	 */
	public static <T extends Comparable<? super T>> void selectionSort(T[] arr) {
		int len = arr.length;
		int min = 0;// 最小或者最大下标
		for (int i = 0; i < len; i++) {
			min = i;
			// 在未排序元素中继续寻找最小元素，并保存其下标
			for (int j = i + 1; j < len; j++) {
				// >0升序   <0降序
				if (arr[min].compareTo(arr[j]) > 0) {
					min = j;
				}
			}
			
			T temp = arr[min];
			arr[min] = arr[i];
			arr[i] = temp;
		}
	}
	
	
	
	/**
	 * 桶排序
	 * 将数据放到相应的桶内，再将每一个桶内的数据进行排序，
	 * 最后把所有桶内数据按照顺序取出来，得到的就是我们需要的有序数据
	 * @param arr
	 */
	public static <T extends Comparable<? super T>> void bucketSort(T[] arr) {
		T max = arr[0], min = arr[0];
		for (T t : arr) {
			if (max.compareTo(t) < 0) {
				max = t;
			}
			if (min.compareTo(t) > 0) {
				min = t;
			}
		}
		
		// 计算桶的数量，此处根据实际计算
		int bucketNum = 10;
		List<ArrayList<T>> bucketList = new ArrayList<ArrayList<T>>();
		// 创建桶
		for (int i = 0; i < bucketNum; i++) {
			bucketList.add(new ArrayList<T>());
		}
		
		// 把数据放入桶中
		for (int i = 0, len = arr.length; i < len; i++) {
			// ??????????---有问题
			int index = Integer.valueOf(arr[i].toString()) / bucketNum;
			bucketList.get(index).add(arr[i]);
		}
		
		// 对每个桶再排序
		int index = 0;
		for (ArrayList<T> arrayList : bucketList) {
			insertSort(arrayList);
			for (T t : arrayList) {
				arr[index++] = t;
			}
		}
	}
	
	// 把桶内元素插入排序
    private static <T extends Comparable<? super T>> void insertSort(ArrayList<T> bucket){
        for (int i = 1; i < bucket.size(); i++){
            T temp = bucket.get(i);
            int j = i - 1;
            for (; j >= 0 && bucket.get(j).compareTo(temp) > 0; j--){
                bucket.set(j+1, bucket.get(j));
            }
            bucket.set(j+1,temp);
        }
    }
	
	
	
}
